//+--------------------------------------------------------------------------------
//| Copyright (c) 2012 - 2013 ### an.vuongngocduy
//| This file is a part of Compact Game Engine (CGE)
//+--------------------------------------------------------------------------------
#ifndef __CGE_LINKEDLIST_H__
#define __CGE_LINKEDLIST_H__

#include "cgeList.h"

namespace cge
{
	namespace std
	{
		//! Basic doubly linked list
		template<class TVal>
		class LinkedList : public List<TVal>
		{
		public:
			//! List node structure
			struct ListNode
			{
				ListNode() : Next(null), Prev(null) {}

				ListNode(const TVal& val) : Next(null), Prev(null), Value(val) {}

				TVal Value;
				ListNode* Next;
				ListNode* Prev;
			};


		public:
			//! Default constructor
			LinkedList()
				: mHead(null), mTail(null), mNumNodes(0)
			{}


			//! Copy constructor.
			LinkedList(const LinkedList& lkLs)
				: mHead(null), mTail(null), mNumNodes(0)
			{
				*this = lkLs;
			}


			//! Construct new LinkedList from a specified list.
			LinkedList(const List<TVal>& ls)
				: mHead(null), mTail(null), mNumNodes(0)
			{
				*this = ls;
			}


			//! Construct new LinkedList by copying array of objects
			LinkedList(const TVal* arr, u32 count)
				: mHead(null), mTail(null), mNumNodes(0)
			{
				for(u32 i = 0; i < count; i++)
					insert(mNumNodes, arr[i]);
			}


			//! Destructor
			~LinkedList()
			{
				clear();
			}
			

			//! Assign operator . Copy content of specified list into current list
			LinkedList& operator = (const LinkedList& lkLs)
			{
				return (*this = (List<TVal>&)lkLs);
			}

			LinkedList& operator = (const List<TVal>& ls)
			{
				clear(); //remove all nodes

				for(u32 i = 0; i < ls.Size(); i++)
					insert(mSize, ls.Get(i));

				return *this;
			}


			//! Cast to base List class.
			operator List<TVal>& () const
			{
				return *((List<TVal>*)this);
			}


		private:
			//! @implements List::count()
			u32 count() const
			{
				return mNumNodes;
			}
			

			//! @implements List::get()
			TVal get(u32 idx) const
			{
				if(idx == 0)
					return mHead->Value;
				else if(idx == mNumNodes - 1)
					return mTail->Value;
				else
				{
					ListNode* cur = null;
					u32 midIdx = mNumNodes / 2;
					if(midIdx >= idx)
					{
						cur = mHead;
						for(u32 i = 0; i < idx; i++, cur = cur->Next);
					}
					else
					{
						cur = mTail;
						for(u32 i = mNumNodes - 1; i > idx; i--, cur = cur->Prev);
					}
					return cur->Value;
				}
			}


			//! @implements List::set()
			void set(u32 idx, const TVal& val)
			{
				if(idx == 0)
					mHead->Value = val;
				else if(idx == mNumNodes - 1)
					mTail->Value = val;
				else
				{
					ListNode* cur = null;
					u32 midIdx = mNumNodes / 2;
					if(midIdx >= idx)
					{
						cur = mHead;
						for(u32 i = 0; i < idx; i++, cur = cur->Next);
					}
					else
					{
						cur = mTail;
						for(u32 i = mNumNodes - 1; i > idx; i--, cur = cur->Prev);
					}
					cur->Value = val;
				}
			}


			//! @implements List::insert()
			b8 insert(u32 idx, const TVal& val)
			{
				if(idx > mNumNodes)
					return false;

				ListNode* node = new ListNode(val);
				
				if(node == null) return false; // out of memory ?

				if(mNumNodes > 0)
				{
					if(idx == 0)
					{
						node->Next = mHead;
						mHead->Prev = node;
						mHead = node;
					}
					else if(idx == mNumNodes)
					{
						node->Prev = mTail;
						mTail->Next = node;
						mTail = node;
					}
					else
					{
						ListNode* cur = null;
						u32 midIdx = mNumNodes / 2;
						if(midIdx >= idx)
						{
							cur = mHead;
							for(u32 i = 0; i < idx; i++, cur = cur->Next);
						}
						else
						{
							cur = mTail;
							for(u32 i = mNumNodes - 1; i > idx; i-- , cur = cur->Prev);
						}
						node->Next = cur;
						node->Prev = cur->Prev;
						cur->Prev->Next = node;
						cur->Prev = node;
					}
				}
				else
					mHead = mTail = node;

				mNumNodes++;
				return true;
			}


			//! @implements List::remove()
			void remove(u32 idx)
			{
				if(idx >= mNumNodes) 
					return;

				ListNode* cur = mHead;
				u32 midIdx = mNumNodes / 2;
				if(midIdx >= idx)
				{
					cur = mHead;
					for(u32 i = 0; i < idx; i++, cur = cur->Next);
				}
				else
				{
					cur = mTail;
					for(u32 i = mNumNodes - 1; i > idx; i-- , cur = cur->Prev);
				}

				if(cur != mHead)
					cur->Prev->Next = cur->Next;
				else
					mHead = mHead->Next;

				if(cur != mTail)
					cur->Next->Prev = cur->Prev;
				else
					mTail = mTail->Prev;

				cur->Prev = cur->Next = null;
				
				delete cur;

				mNumNodes--;
			}


			//! @implements List::clear()
			void clear()
			{
				if(mNumNodes > 0)
				{
					ListNode* cur = mHead;
					while(cur != null)
					{
						ListNode* next = cur->Next;
						delete cur;
						cur = next;
						mNumNodes--;
					}
				}
			}


		private:
			ListNode* mHead;
			ListNode* mTail;
			u32 mNumNodes;
		};
	}
}

#endif//__CGE_LINKEDLIST_H__